Finding hypernetworks in directed hypergraphs

The term “hypernetwork” (more precisely, s-hypernetwork and (s, d)-hypernetwork) has been recently adopted to denote some logical structures contained in a directed hypergraph. A hypernetwork identifies the core of a hypergraph model, obtained by filtering off redundant components. Therefore, finding hypernetworks has a notable relevance both from a theoretical and from a computational point of view.     

Maximal τ-Critical Linear Hypergraphs

 A construction using finite affine geometries is given to show that the maximum number of edges in a τ-critical linear hypergraph is (1−o(1))τ². This asymptotically answers a question of Roudneff [14], Aharoni and Ziv [1]. Received: June 28, 1999 Final version received: October 22, 1999     

Total Domination in Graphs with Diameter 2

The total domination number of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, . This bound is optimal in the sense that given any , there exist graphs G with diameter 2 of all sufficiently large even orders n such that .     

On independent sets in hypergraphs

The independence number of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove that if H_n is an n‐vertex ‐uniform hypergraph in which every r‐element set is contained in at most d edges, where , then where satisfies as . The value of c_r improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi (J Comb Theory Ser A 32 (1982), 321–335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269–271) and Alon (Random Struct Algorithms 9 (1996), 271–278). The above statement is close to best possible, in the sense that for each and all values of , there are infinitely many H_n such that where depends only on r. In addition, for many values of d we show as , so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224‐239, 2014     

超图的某些参数间的关系

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows: DV(H) ≤DV(H) α(H) ≤ n; 2 ≤ DV (H) τ(H) ≤ n; 2 ≤ DV(H) v(H) ≤ n/2 [n/r]; DV (H) ρ(H) ≤n;2 ≤ De(H) DV(H) ≤ n/2 [n/r];α(H) De(H) ≤ n;2 ≤ De(H) v(H) ≤ 2[n/r];2 ≤De(H) ρ(H) ≤ n- r 2.     

关于不含k-C-圈的n阶γ-一致超图的若干结果

主要讨论了不含k-C-圈的n阶γ-一致超图,对不同的k, 分别得出了它的极大边数的一个下界,并且得出在有些情况下它的下界是最大的.另外,我们得到了Krn含k-C-圈的一个充分必要条件.     

Finding the K shortest hyperpaths using reoptimization

We present some reoptimization techniques for computing (shortest) hyperpath weights in a directed hypergraph. These techniques are exploited to improve the worst-case computational complexity (as well as the practical performance) of an algorithm finding the K shortest hyperpaths in acyclic hypergraphs.     

A note on near‐optimal coloring of shift hypergraphs

As shown in the original work on the Lovász Local Lemma due to Erd?s & Lovász (Infinite and Finite Sets, 1975), a basic application of the Local Lemma answers an infinitary coloring question of Strauss, showing that given any integer set S, the integers may be k‐colored so that S and all its translates meet every color. The quantitative bounds here were improved by Alon, Kriz & Nesetril (Studia Scientiarum Mathematicarum Hungarica, 1995). We obtain an asymptotically optimal bound in this note, using the technique of iteratively applying the Lovász Local Lemma in order to prune dependencies. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 53–56, 2016